/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */
#include "packet-reorder-calculator.h"
#include "ns3/log.h"
#include "ns3/simulator.h"
#include "ns3/trace-source-accessor.h"
#include "ns3/string.h"
#include <algorithm>
#include <list>
#include <utility>

NS_LOG_COMPONENT_DEFINE ("PacketReorderCalculator");

namespace ns3 {
namespace eecityu {

using namespace std;

class DelayJitterEstimationTimestampTag : public Tag
{
public:
  DelayJitterEstimationTimestampTag ();
  static TypeId GetTypeId (void);
  virtual TypeId GetInstanceTypeId (void) const;

  virtual uint32_t GetSerializedSize (void) const;
  virtual void Serialize (TagBuffer i) const;
  virtual void Deserialize (TagBuffer i);
  virtual void Print (std::ostream &os) const;

  Time GetTxTime (void) const;
private:
  uint64_t m_creationTime;
};

DelayJitterEstimationTimestampTag::DelayJitterEstimationTimestampTag ()
  : m_creationTime (Simulator::Now ().GetTimeStep ())
{}

TypeId 
DelayJitterEstimationTimestampTag::GetTypeId (void)
{
  static TypeId tid = TypeId ("anon::DelayJitterEstimationTimestampTag")
    .SetParent<Tag> ()
    .AddConstructor<DelayJitterEstimationTimestampTag> ()
    .AddAttribute ("CreationTime",
		   "The time at which the timestamp was created",
		   StringValue ("0.0s"),
		   MakeTimeAccessor (&DelayJitterEstimationTimestampTag::GetTxTime),
		   MakeTimeChecker ())
    ;
  return tid;
}
TypeId 
DelayJitterEstimationTimestampTag::GetInstanceTypeId (void) const
{
  return GetTypeId ();
}

uint32_t 
DelayJitterEstimationTimestampTag::GetSerializedSize (void) const
{
  return 8;
}
void 
DelayJitterEstimationTimestampTag::Serialize (TagBuffer i) const
{
  i.WriteU64 (m_creationTime);
}
void 
DelayJitterEstimationTimestampTag::Deserialize (TagBuffer i)
{
  m_creationTime = i.ReadU64 ();
}
void 
DelayJitterEstimationTimestampTag::Print (std::ostream &os) const
{
  os << "CreationTime=" << m_creationTime;
}
Time 
DelayJitterEstimationTimestampTag::GetTxTime (void) const
{
  return TimeStep (m_creationTime);
}

NS_OBJECT_ENSURE_REGISTERED (PacketReorderCalculator);

TypeId 
PacketReorderCalculator::GetTypeId (void)
{
  static TypeId tid = TypeId ("ns3::PacketReorderCalculator")
    .SetParent<Object> ()
    .AddConstructor<PacketReorderCalculator> ()
    .AddTraceSource ("DuplicatedRx", 
                     "A duplicated packet is received",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_duplicatedPktRxTrace))
    .AddTraceSource ("ReorderedRx", 
                     "A reordered packet is received",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_reorderedPktRxTrace))    
    .AddTraceSource ("PacketRx", 
                     "A packet is received",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_pktRxTrace))   
    .AddTraceSource ("PacketTx", 
                     "A packet is transmitted",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_pktTxTrace))   
    .AddTraceSource ("ReorderExtentRx", 
                     "Get the reordering extent of each reordered packet",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_reorderedExtentRxTrace))   
    .AddTraceSource ("LateTimeRx", 
                     "Get the late-time of each reordered packet",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_reorderedLateTimeRxTrace))   
    .AddTraceSource ("DelayRx", 
                     "Get the transienting delay of each received packet",
                     MakeTraceSourceAccessor (&PacketReorderCalculator::m_transitingDelayRxTrace))  
                     ;
  return tid;
}

PacketReorderCalculator::PacketReorderCalculator(void)
  : m_nextExp (0), m_nextRxIndex (0), m_nextTxSeqNum (0)
  , m_totalNumPacketsSent (0), m_totalBytesSent (0)
{
  NS_LOG_FUNCTION (m_nextExp);
}

PacketReorderCalculator::~PacketReorderCalculator (void)
{}

uint64_t 
PacketReorderCalculator::PrepareTx (Ptr<const Packet> packet)
{
  NS_LOG_FUNCTION (packet->GetUid ());

  // Add a DelayJitterEstimationTimestampTag to the packet, allowing the 
  // receiving end to now the departure time of the packet
  m_delayJitterEstimator.PrepareTx (packet);
  // Count the total number of pakets and bytes sent from the source
  m_totalNumPacketsSent++;
  m_totalBytesSent += packet->GetSize ();

  // Add a tag to the packet for marking the sequence number of this packet
  //
  // as the sequence starts from one, it is post-incremented when being
  // assigned to this tag
  PacketReorderCalculatorTag tag;
  tag.SetSeqNum (m_nextTxSeqNum++);
  packet->AddPacketTag (tag);

  m_pktTxTrace ();

  NS_LOG_LOGIC ("Next expacted arrival sequence number = " << m_nextExp);
  return tag.GetSeqNum ();
}

uint64_t 
PacketReorderCalculator::RecordRx (Ptr<const Packet> packet)
{
  NS_LOG_FUNCTION (packet->GetUid ());
  NS_LOG_LOGIC ("The expected sequence number = " << m_nextExp);

  // record this received packet so that packet transiting delay and 
  // delay jitter can be measured or be estimated
  m_delayJitterEstimator.RecordRx (packet);
  m_transitingDelayRxTrace (m_delayJitterEstimator.GetLastDelay ());
  // Obtain the ttl value and calculate the number of hops the packet transerved
  
  // record the information regarding the arrival of this packet
  PacketArrivalRecord arrival;
  // record the index for this arrival packet
  arrival.rxIndex = m_nextRxIndex;
  // record the packet size
  arrival.packetSize = packet->GetSize ();
  // record the packet arrival time
  arrival.rxTime = Simulator::Now ();
  // record the packet trasmission time
  DelayJitterEstimationTimestampTag djTag;
  bool found = packet->FindFirstMatchingByteTag (djTag);
  NS_ASSERT_MSG (found, "DelayJitterEstimationTimestampTag is not found! "
    << "Unable to calculate packet reordering metrics");
  arrival.txTime = djTag.GetTxTime ();
  // record the packet sequence number
  PacketReorderCalculatorTag sqTag;
  found = packet->PeekPacketTag (sqTag);
  NS_ASSERT_MSG (found, "PacketReorderCalculatorTag is not found! "
    << "Unable to calcualate packet reordering metrics.");
  arrival.seqNum = sqTag.GetSeqNum ();

  // check if the current packet recorded is Type-P-Reordered according
  // to Section 3.1 of RFC 4737
  //
  // If this is true, the current arrival packet is Type-P-Reordered
  bool type_P_Reordered;
  // Check for any sequence discontinuity. Founding such discontinuity can
  // speed up the calculation of the Type-P-Packet-Reordering-Extent-Stream
  // defined in Section 4.2 of RFC 4737.
  bool sequenceDiscontinuty;
  // The number of packets that are expected to be received already but now missing
  uint64_t seqDiscontinutySize;
  // Update the states of this object for proper reception of arrival packets
  UpdateRx (arrival, type_P_Reordered, sequenceDiscontinuty, seqDiscontinutySize);
  NS_LOG_LOGIC ("type_P_Reordered = " << type_P_Reordered);
  NS_LOG_LOGIC ("sequenceDiscontinuty = " << sequenceDiscontinuty);
  NS_LOG_LOGIC ("Sequence number of the arrival = " << arrival.seqNum);
  NS_LOG_LOGIC ("Next expected sequence number = " << m_nextExp);
  NS_LOG_LOGIC ("Next recpetion index = " << m_nextRxIndex);
 
  // Create records for those missing packets. Packets that fall into the range of
  // sequence discontinuity belongs to the missing record
  if (sequenceDiscontinuty)
  {
    NS_LOG_LOGIC ("Sequence discontinuity found with size = " << seqDiscontinutySize);
    AddToMissingRecord (
      arrival.seqNum - seqDiscontinutySize, 
      arrival.seqNum - 1
      );
    // add this record into the "missing range end" set for helping the
    // calculation of reordering extent
    AddToMissingRangeEnd (arrival);
    NS_LOG_LOGIC ("Added to the \"missing range end\" set the record with sequence number = " 
      << arrival.seqNum
      );
  }
  if (type_P_Reordered)
  {
    NS_LOG_LOGIC ("type_P_Reordered found for the arrival "
      << "packet with sequence number = " << arrival.seqNum);
    // Try adding the arrival packet into the duplicated record map. The method returns false
    // and blocks the add operation if the packet indeed is not a duplication
    bool isDuplicated = AddToDuplicatedRecord (arrival);
    NS_LOG_LOGIC ("The arrival packet is a duplication = " << isDuplicated);
    if (!isDuplicated) 
    {
      // Add the record of this arrival packet into the reordered 
      // record set if this packet is reordered
      AddToReorderRecord (arrival);
      NS_LOG_LOGIC ("Added the arrival packet into the reordered record set");
    }
  }

  m_pktRxTrace ();

  // return the sequence number of this arrival packet
  return sqTag.GetSeqNum ();
}

void 
PacketReorderCalculator::UpdateRx (
  const PacketArrivalRecord& arrival,
  bool& type_P_Reordered,
  bool& sequenceDiscontinuty,
  uint64_t& seqDiscontinutySize)
{
  NS_LOG_FUNCTION (arrival.seqNum << type_P_Reordered << sequenceDiscontinuty << seqDiscontinutySize);

  NS_LOG_LOGIC ("Arrival sequence number = " << arrival.seqNum 
    << ", expected sequence number = " << m_nextExp);
  if (arrival.seqNum >= m_nextExp) 
  {
    if (arrival.seqNum > m_nextExp)
    {
      NS_LOG_LOGIC ("Sequence discontinuity found during arrival packet reception");
      sequenceDiscontinuty = true;
      seqDiscontinutySize = arrival.seqNum - m_nextExp;
    }
    else
    {
      NS_LOG_LOGIC ("Next expected packet received");
      sequenceDiscontinuty = false;
    }
    m_nextExp = arrival.seqNum + 1;
    type_P_Reordered = false;
  }
  else      
  {
    NS_LOG_LOGIC ("Packet reordered found during arrival packet reception");
    type_P_Reordered = true;
    sequenceDiscontinuty = false;
  }
  NS_LOG_LOGIC ("Expected sequence number for the next arrival = " << m_nextExp);
  // increment the index of packet reception
  m_nextRxIndex++;
}

uint32_t 
PacketReorderCalculator::GetNArrival () const
{
  return m_nextRxIndex;
}

uint32_t 
PacketReorderCalculator::GetNDuplicated () const
{
  return (uint32_t) m_duplicatedRecordMap.size ();
}

uint32_t 
PacketReorderCalculator::GetNMissing () const
{
  // Number of packets recorded as missing
  uint32_t listSize = (uint32_t) m_missingRecordList.size ();
  NS_LOG_INFO ("Number of missing packets known = " << listSize);
  // Number of packets that are currently on the fly to the destination
  NS_ASSERT_MSG (m_nextTxSeqNum >= m_nextExp, 
    "Miss-aligned sequence number among sender and receiver! "
    << "Sender sequence number must be equal or larger than the "
    << "sequence number expected by a receiver.");
  uint32_t onTheFly = m_nextTxSeqNum - m_nextExp;
  NS_LOG_INFO ("Number of packets on the fly = " << onTheFly);
  for (list<PacketArrivalRecord>::const_iterator 
    it = m_missingRecordList.begin ();
    it != m_missingRecordList.end (); it++)
  {
    NS_LOG_INFO ("missing packet seq = " << it->seqNum << ", rxIndex = " << it->rxIndex);
  }
  return listSize + onTheFly;
}

uint32_t 
PacketReorderCalculator::GetNReordered () const
{
  return m_reorderRecordSet.size ();
}

uint64_t 
PacketReorderCalculator::GetNPacketsSent () const
{
  return m_totalNumPacketsSent;
}

uint64_t 
PacketReorderCalculator::GetNBytesSent () const
{
  return m_totalBytesSent;
}

bool 
PacketReorderCalculator::IsMissing (uint64_t s) const
{
  NS_LOG_FUNCTION (s);

  return find (m_missingRecordList.begin (), 
    m_missingRecordList.end (), PacketArrivalRecord (s)
    ) != m_missingRecordList.end ();
}

bool 
PacketReorderCalculator::IsReordered (uint64_t s) const
{
  NS_LOG_FUNCTION (s);

  set<PacketArrivalRecord>::iterator dummy;
  return IsReordered (s, dummy);
}

bool 
PacketReorderCalculator::IsReordered (uint64_t s, set<PacketArrivalRecord>::iterator& iter) const
{
  NS_LOG_FUNCTION (s << "iter");

  iter = m_reorderRecordSet.find (PacketArrivalRecord (s));
  return iter != m_reorderRecordSet.end ();
}

Time 
PacketReorderCalculator::GetLateTime (uint64_t s) const
{
  NS_LOG_FUNCTION (s);

  typedef set<PacketArrivalRecord> Set_t;
  typedef Set_t::iterator Iter_t;

  // An iterator pointing to the record of "s" in the reordered record set
  Iter_t s_iter;
  // An iterator pointing to the "earliest upper bound" record of the packet "s"
  Iter_t earliestUb_iter;
  uint64_t reorderingExtent = GetReorderingExtent (s, s_iter, earliestUb_iter);
  NS_LOG_LOGIC ("Reordering extent of packet " << s << " = " << reorderingExtent);
  // The time value to be returned
  Time ret ("0s");
  if (reorderingExtent == 0) {}
    // return the default value of "ret" if the packet is in-ordered
  else
    // return the reordered late time if the packet is reordered
    ret = s_iter->rxTime - earliestUb_iter->rxTime;

  return ret;
}

uint64_t 
PacketReorderCalculator::GetReorderingExtent (uint64_t s) const
{
  NS_LOG_FUNCTION (s);

  set<PacketArrivalRecord>::iterator dummy1, dummy2;
  return GetReorderingExtent (s, dummy1, dummy2);
}

/*
 * This is the base method for calculating reordering extent and reordering late time defined in RFC4737. 
 * The "earliest upper bound" record of the packet "s" is the most important information to calculate the 
 * two metrics. The "earliest upper bound" record refers to the earliest record that are 
 * both received successfully and whose sequence number is larger than "s".
 */
uint64_t 
PacketReorderCalculator::GetReorderingExtent (
  uint64_t s, 
  set<PacketArrivalRecord>::iterator& s_iter,
  set<PacketArrivalRecord>::iterator& earliestUb_iter) const
{
  NS_LOG_FUNCTION (s);

  typedef set<PacketArrivalRecord> Set_t;
  typedef Set_t::iterator Iter_t;
  // the reordering extent value to be returned
  uint64_t extent;
  // see if the packet with sequence number 's' is reordred. If not, return 0
  // At the same time, return to "s_iter" the iterator pointing to the reordered 
  // packet record in the reordered record set
  bool isReordered = IsReordered (s, s_iter);
  if (!isReordered)
    extent = 0;
  else
  {
    // found the record for the packet that is received successfully and is received
    // immediately after the packet with sequence number 's'
    earliestUb_iter = m_missingRangeEndSet.lower_bound (PacketArrivalRecord (s));
    bool found = (earliestUb_iter != m_missingRangeEndSet.end ());
    NS_ASSERT_MSG (found, "A earliest-upper-bound record for the missing sequence number " 
      << s << " is not found!");
    NS_ASSERT_MSG (s_iter->rxIndex > earliestUb_iter->rxIndex, 
      "Error! Receiption index for the reordered packet must be "
      << "strictly larger than the packet's with which the reordering "
      << "extent is calculated.");
    NS_LOG_LOGIC ("Queried packet " << s 
      << " received on index " << s_iter->rxIndex 
      << " at time " << s_iter->rxTime.GetSeconds ());
    NS_LOG_LOGIC ("\"Earliest-upper-bound\" packet " << earliestUb_iter->seqNum 
      << " received on index " << earliestUb_iter->rxIndex 
      << " at time " << earliestUb_iter->rxTime.GetSeconds ());
    extent = s_iter->rxIndex - earliestUb_iter->rxIndex;    
  }
  NS_LOG_LOGIC ("Reordering extent for packet (" << s << ") = " << extent);
  return extent;
}

void 
PacketReorderCalculator::DoDispose (void)
{
  NS_LOG_FUNCTION_NOARGS ();

  m_duplicatedRecordMap.clear ();
  m_reorderRecordSet.clear ();
  m_missingRecordList.clear ();
  m_missingRangeEndSet.clear ();

  Object::DoDispose ();
}

void 
PacketReorderCalculator::AddToMissingRecord (uint64_t s1, uint64_t s2)
{
  NS_LOG_FUNCTION (s1 << s2);
  NS_ASSERT_MSG (s2 >= s1, "Invalid range!");
  // check if the proper ordering among missing records are honoreds
  if (!m_missingRecordList.empty ())
  {
    NS_LOG_LOGIC ("Checking for the proper ordering among the missing records");
    // the last and the largest sequence number in the missing records
    uint64_t maxS = m_missingRecordList.back ().seqNum;
    NS_ASSERT_MSG (s1 > maxS, "Invalid ordering among missing records. The addition of the new "
      << "range of sequence numbers destructs proper ordering of the existing sequence numbers, "
      << "where they must be monotonic increasing.");
  }

  // walk through the entire range enclosed by s1 and s2, inclusive, and add
  // add all these sequence numbers into the missing records
  while (s1 <= s2)  
  {
    PacketArrivalRecord missr (s1++);
    NS_LOG_LOGIC ("Adding record to the missing record list whose sequence number = " << missr.seqNum);
    m_missingRecordList.push_back (missr);
  }
}

void 
PacketReorderCalculator::AddToReorderRecord (PacketArrivalRecord r)
{
  NS_LOG_FUNCTION (&r);

  typedef list<PacketArrivalRecord> List_t;
  typedef List_t::iterator Iter_t;
  // An iterator pointing to the 'r' record in the missing records.
  Iter_t rInMissingIter = find (m_missingRecordList.begin (), m_missingRecordList.end (), r);
  NS_ASSERT_MSG (rInMissingIter != m_missingRecordList.end (), "The arrival packet "
    << "does not recorded in the missing record! A packet intended to be in the "
    << "reordered record must first exist in the missing record. If this rule is "
    << "violated, the packet may actually is a duplicated packet and should go to "
    << "the duplicated record instead.");
  // Update the reordered record. It has a valid sequence only at this moment
  rInMissingIter->packetSize = r.packetSize;
  rInMissingIter->rxIndex = r.rxIndex;
  rInMissingIter->rxTime = r.rxTime;
  rInMissingIter->txTime = r.txTime;
  // Move the arrival record from missing record to reordered record. This move is done
  // by first adding the record into the reordered record, and then remove the record
  // from the missing record.
  //
  // Record the arrival packet into reordered record
  NS_LOG_DEBUG ("rInMissingIter->seqNum = " << rInMissingIter->seqNum);
  bool isNew = m_reorderRecordSet.insert (*rInMissingIter).second;
  NS_ASSERT_MSG (isNew, "Duplicated record found in the reordered record! "
    << "This arrival packet may better belong to duplicated record.");
  // Trace sources for reordered packets
  m_reorderedPktRxTrace ();
  m_reorderedExtentRxTrace (GetReorderingExtent (r.seqNum));
  m_reorderedLateTimeRxTrace (GetLateTime (r.seqNum));
  // remove the 'r' record from the missing record
  //
  // Check if the removal is successful by reading the change of the list's size
  List_t::size_type sizeBefore = m_missingRecordList.size ();
  m_missingRecordList.erase (rInMissingIter);
  List_t::size_type sizeAfter = m_missingRecordList.size ();
  NS_ASSERT_MSG (sizeAfter == (sizeBefore - 1), 
    "Unable to erase the record from the missing record list!");
}

bool 
PacketReorderCalculator::AddToDuplicatedRecord (PacketArrivalRecord r)
{
  NS_LOG_FUNCTION (&r);
  // test if the arrival packet has been recorded in the missing record list
  bool found = 
    find (m_missingRecordList.begin (), m_missingRecordList.end (), r) 
    != m_missingRecordList.end ();
  if (!found)
  {
    // record this packet in the duplicated packet map, and count the number
    // duplication seen
    uint32_t dupCount = ++(m_duplicatedRecordMap [r]);
    NS_LOG_LOGIC ("Found a duplicated packet for " << dupCount 
      << " times whose sequence number = " << r.seqNum);
    m_duplicatedPktRxTrace ();
  }

  return !found;
}

void 
PacketReorderCalculator::AddToMissingRangeEnd (PacketArrivalRecord r)
{
  bool isNew = m_missingRangeEndSet.insert (r).second;
  NS_ASSERT_MSG (isNew, "Error! The packet arrival record already exists in the \"missing range end\" set.");
}

PacketReorderCalculator::PacketArrivalRecord::PacketArrivalRecord ()
  : seqNum ( (uint64_t) -1)
{
}

PacketReorderCalculator::PacketArrivalRecord::PacketArrivalRecord (uint64_t s)
  : seqNum (s)
{
}

// The core method to define the order among PacketArrivalRecord objects
bool 
PacketReorderCalculator::PacketArrivalRecord::operator <  (const PacketArrivalRecord& r) const
{
  return seqNum < r.seqNum;
}

bool 
PacketReorderCalculator::PacketArrivalRecord::operator >  (const PacketArrivalRecord& r) const
{
  return r < (*this);
}

bool 
PacketReorderCalculator::PacketArrivalRecord::operator >= (const PacketArrivalRecord& r) const
{
  return !( (*this) < r );
}

bool 
PacketReorderCalculator::PacketArrivalRecord::operator <= (const PacketArrivalRecord& r) const
{
  return !( (*this) > r );
}

bool 
PacketReorderCalculator::PacketArrivalRecord::operator == (const PacketArrivalRecord& r) const
{
  return ( (*this) <= r ) && ( (*this) >= r );
}


bool 
PacketReorderCalculator::PacketArrivalRecord::operator != (const PacketArrivalRecord& r) const
{
  return !( (*this) == r );
}





} // namespace eecityu
} // namespace ns3
